// 二叉树
class Node {
  constructor (key) {
    this.key = key // 节点值
    this.left = null // 左侧节点的引用
    this.right = null // 右侧节点的引用
  }
}
// 二叉树 的数据存储  数组或链表
// 使用数组的形式
function arrayBuildTree (arr) {
  return helper(arr, 0)
}
function helper (arr, index) {
  // 进行非空判断
  if (index > arr.length || arr[index] == null || arr[index] == undefined) return null
  const root = new Node(arr[index])
  root.left = helper(arr, 2 * index + 1)
  root.right = helper(arr, 2 * index + 2)
  return root
}
/**
 * 二叉搜索树的特征: 若左子树不为空 则左子树上所有节点的值 均小于或等于他的根节点的值 2 若右子树
 * 不为空 则右子树上所有节点的值均大于或者等于他的根节点的值 左右子树也分别为二叉搜索树
 * 二叉搜索树的中序遍历结果就是二叉搜索树所有节点从小到大的排序结果
 */
// 使用链表的形式
class BinarySearchTree {
  constructor () {
    this.root = null
  }
  // 二叉搜索树的常见操作
  // 向数中插入一个新的键
  insert (key) {
    // 创建节点
    let node = new Node(key)
    if (this.root == null) {
      this.root = node
    } else {
      this.insertNode(this.root, node)
    }
  }
  insertNode (root, node) {
    if (node.key < root.key) {
      if (root.left === null) {
        root.left = node
      } else {
        this.insertNode(root.left, node)
      }
    } else {
      if (root.right === null) {
        root.right = node
      } else {
        this.insertNode(root.right, node)
      }
    }
  }
  // 返回树中最小的值/键
  min () {
    if (!this.root) return null;
    let node = this.root;
    while (node.left !== null) {
      node = node.left;
    }
    return node.key;
  }
  // 返回二叉树中的最大值
  max () {
    if (!this.root) return null;
    let node = this.root;
    while (node.right !== null) {
      node = node.right;
    }
    return node.key;
  }
  // 查找某个值是否存在于二叉树中
  search (key) {
    return this.searchNode(this.root, key)
  }
  searchNode (root, key) {
    if (root === null) return false
    while (root !== null) {
      if (key < root.key) {
        node = root.left
      } else if (key > root.key) {
        node = node.right
      } else {
        return true
      }
    }
    return false
  }
  // 删除节点
  remove (key) {
    let curNode = this.root // 用于保存需要删除的节点
    let parentNode = null // 保存需要删除的父节点
    let isLeftChild = true // 保存(待删除的节点是否为要删除节点的父节点)
    // 查找需要删除的节点 以及他的父节点
    while (curNode.key !== key) {
      parentNode = curNode
      // 当key 小于当前节点的key 说明只需要去当前节点的左叶子树查找
      if (key < curNode.key) {
        isLeftChild = true
        curNode = curNode.left
      } else {
        // 存在于右边
        isLeftChild = false
        curNode = curNode.right
      }
      // 节点不存在时
      if (curNode === null) {
        return -1
      }
    }
    // 当找到要删除节点后
    // 1. 如果删除的是叶子节点的情况
    if (curNode.left === null && curNode.right === null) {
      if (curNode === this.root) {
        this.root = null
      } else if (isLeftChild) {
        parentNode.left = null
      } else {
        parentNode.right = null
      }
    } else if (curNode.right === null) { // 要删除的节点只存在于左节点
      // 
    }
  }
}
function at (list) {
  let node = new BinarySearchTree()
  for (let i = 0; i < list.length; i++) {
    node.insert(list[i])
  }
  console.log(JSON.stringify(node));
}
const binarySearchTree = new BinarySearchTree()
at([11, 7, 5, 3, 9, 8, 10, 15, 13, 12, 14, 20, 18, 25, 19])
binarySearchTree.insert(3);
binarySearchTree.insert(9);
binarySearchTree.insert(20);
binarySearchTree.insert(15);
binarySearchTree.insert(7);

console.log(JSON.stringify(binarySearchTree));
console.log(binarySearchTree.min());
console.log(binarySearchTree.max());